class Solution1 {
    public int jump(int[] nums) {
        int count = 0;
        int n = nums.length;
        if (n == 1) return 0;
        int i = 0;
        while (i < n) {
            if (i + nums[i] >= n - 1) {
                count++;
                break;
            }

            int max = 0, index = 0;
            //寻找 i~i+nums[i] 之间的最大值
            int j;
            for (j = i + 1; j < n && j <= i + nums[i]; j++) {
                if (nums[j] >= max) {
                    max = nums[j];
                    index = j;
                }
            }
            i = index;
            count++;
        }
        return count;
    }
}

class Solution2 {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 1; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(i - j <= nums[j]) {
                    dp[i] = Math.min(dp[j] + 1, dp[i]);
                }
            }
        }
        return dp[n - 1];
    }
}

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int count = 0;
        int left = 0, right = 0;
        int i = 0;
        while(i < n) {
            int newLeft = right + 1;
            int newRight = 0;
            for(int j = left; j<=right; j++) {
                newRight = Math.max(newRight, nums[j] + j);
            }

            left = newLeft;
            right = newRight;
            i = left;
            if(left >= n) break;;
            count++;
        }
        return count;
    }
}

// dp[i] =

public class Test {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3};
        int[] nums2 = {2, 3, 1, 1, 4};
        int[] nums3 = {1, 2, 1, 1, 1};
        int ret = new Solution().jump(nums3);
        System.out.println(ret);
    }
}
